// Arrangment and permutation
// 排列（元素有重不可复选）
// [排列]
// 题目给你输入一个无重复元素的数组 nums，
// 其中每个元素最多使用一次，请你返回 nums 的指定大小的排列

#include <bits/stdc++.h>
using namespace std;

template <typename T>
void printVector(vector<T> nums, bool withEnter=true)
{
    for (auto n : nums)
    {
        cout << n << ' ';
    }
    if(withEnter)
        cout<<endl;
}


vector<vector<int>> res;
vector<int> path;
vector<bool> used;

void backtrack(vector<int> &nums){
    if(path.size() == nums.size()){
        res.push_back(path);
        return;
    }

    for(int i = 0; i < nums.size(); i++){
        if(used[i]) continue;
        if(i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
        path.push_back(nums[i]);
        used[i] = true;
        backtrack(nums);
        used[i] = false;
        path.pop_back();
        
    }
    return;
}

vector<vector<int>> combine(vector<int> nums, int k){
    sort(nums.begin(),nums.end());
    backtrack(nums);
    return res;
}

int main(){
    vector<int> nums = {1,2,2,2};
    used.resize(nums.size());
    vector<vector<int>> res = combine(nums,3);
    for(auto line : res){
        printVector(line);
    }
    return 0;
}
